Theory Lunch

Faster Minimum k-Cut for Simple Weighted Graphs

Trevor Vaughn

September 2, 2026 (GHC 6501)

The Minimum k-Cut problem asks for the minimum weight of edges that can be removed from a graph for it to have at least k components. We present a n^{k-2} m weighted k-cut algorithm which is used to obtain a faster algorithm for Minimum k-Cut on simple graphs. If time allows, we also present the development in later work of a n^{k-1} algorithm for weighted Minimum k-Cut